/* Investigate current graph properties */

#include <queue>

#include <memchart/types.hpp>

#include "chart_box.hpp"

#include "memory_chart.hpp"

namespace memchart
{
	using std::queue;

	void MemoryChart::make_boxes_unseen ()
	{
		for (box_iter v = boxes.begin(); v != boxes.end(); ++v)
			v->second.seen = false;
	}

	size_t MemoryChart::traverse_list (box_iter & v)
	{
		size_t count = 0;

		make_boxes_unseen();
		while (true)
		{
			count++;
			v->second.seen = true;

			box_iter v2 = boxes.find(v->second.edges[0]);
			if (v2 == boxes.end() || v2->second.seen)
			{
				v2 = boxes.find(v->second.edges[1]);
				if (v2 == boxes.end() || v2->second.seen)
					break;
			}
			v = v2;
		}

		return count;
	}

	void MemoryChart::analyze_graph ()
	{
		if (boxes.size() == 0)
		{
			is_dag = is_list = is_tree = false;
			return;
		}

		/* Check for DAG */

		torder.clear();
		queue<box_iter> q;

		make_boxes_unseen();
		for (box_iter v = boxes.begin(); v != boxes.end(); ++v)
			v->second.parent_count = v->second.level = 0;
		for (box_iter v = boxes.begin(); v != boxes.end(); ++v)
		{
			for (edge_iter e = v->second.edges.begin();
				e != v->second.edges.end(); ++e)
			{
				box_iter v2 = boxes.find(*e);
				if (v2 != boxes.end())
				{
					v2->second.parent_count++;
					v2->second.seen = true;
				}
			}
		}
		for (box_iter v = boxes.begin(); v != boxes.end(); ++v)
		{
			if (!v->second.seen)
				q.push(v);
		}

		while (!q.empty())
		{
			torder.push_back(q.front());
			for (edge_iter e = q.front()->second.edges.begin();
				e != q.front()->second.edges.end(); ++e)
			{
				box_iter v = boxes.find(*e);
				if (v != boxes.end())
				{
					if (--v->second.parent_count == 0)
					{
						v->second.level = q.front()->second.level + 1;
						q.push(v);
					}
				}
			}
			q.pop();
		}

		is_dag = torder.size() == boxes.size();

		/* Check for tree structure */
		is_tree = is_dag &&
			(torder.size() == 1 || torder[1]->second.level != 0);
		if (is_tree)
		{
			make_boxes_unseen();

			queue<box_iter> q;
			q.push(torder[0]);

			while (!q.empty())
			{
				chart_box & box = q.front()->second;
				if (box.seen)
				{
					is_tree = false;
					break;
				}
				box.seen = true;
				for (edge_iter e = box.edges.begin(); e != box.edges.end(); ++e)
				{
					box_iter v = boxes.find(*e);
					if (v != boxes.end())
						q.push(v);
				}

				q.pop();
			}
		}

		/* Check for linked list structure */
		if (is_tree)
		{
			/* Singly-linked list */

			is_list = true;
			box_iter v = torder[0];
			do
			{
				if (v->second.edges.size() != 1)
				{
					is_list = false;
					break;
				}
				v = boxes.find(v->second.edges[0]);
			}
			while (v != boxes.end());
			if (is_list)
				list_head = torder[0];
		}
		else if (!is_dag)
		{
			/* Double-linked list */

			is_list = true;
			for (box_iter v = boxes.begin(); v != boxes.end(); ++v)
			{
				if (v->second.edges.size() != 2)
				{
					is_list = false;
					break;
				}
			}

			if (is_list)
			{
				box_iter v;
				for (v = boxes.begin(); v != boxes.end(); ++v)
				{
					if (boxes.find(v->second.edges[0]) == boxes.end() ||
						boxes.find(v->second.edges[1]) == boxes.end())
					{
						/* This supposedly is the list head */
						break;
					}
				}

				is_list = v != boxes.end() &&
					traverse_list(v) == boxes.size() &&
					traverse_list(v) == boxes.size();
				if (is_list)
					list_head = v;
			}
		}
		else
			is_list = false;
	}
}
